翻訳と辞書 Words near each other ・ Binary chemical weapon ・ Binary classification ・ Binary clock ・ Binary code ・ Binary code compatibility ・ Binary collision approximation ・ Binary combinatory logic ・ Binary compound ・ Binary compounds of hydrogen ・ Binary compounds of silicon ・ Binary constraint ・ Binary cycle ・ Binary cyclic group ・ Binary data ・ Binary decision ・ Binary decision diagram ・ Binary decoder ・ Binary delta compression ・ Binary distribution ・ Binary distribution (disambiguation) ・ Binary Divide ・ Binary Domain ・ Binary economics ・ Binary entropy function ・ Binary erasure channel ・ Binary ethylenimine ・ Binary explosive ・ Binary expression tree ・ Binary file ・ Binary File Descriptor library Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Binary decision diagram ： ウィキペディア英語版 Binary decision diagram In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression. Other data structures used to represent a Boolean function include negation normal form (NNF), propositional directed acyclic graph (PDAG). == Definition == A Boolean function can be represented as a rooted, directed, acyclic graph, which consists of several decision nodes and terminal nodes. There are two types of terminal nodes called 0-terminal and 1-terminal. Each decision node $N$ is labeled by Boolean variable $V\_N$ and has two child nodes called low child and high child. The edge from node $V\_N$ to a low (or high) child represents an assignment of $V\_N$ to 0 (resp. 1). Such a BDD is called 'ordered' if different variables appear in the same order on all paths from the root. A BDD is said to be 'reduced' if the following two rules have been applied to its graph: * Merge any isomorphic subgraphs. * Eliminate any node whose two children are isomorphic. In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD in the literature, used when the ordering and reduction aspects need to be emphasized). The advantage of an ROBDD is that it is canonical (unique) for a particular function and variable order.〔Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986〕 This property makes it useful in functional equivalence checking and other operations like functional technology mapping. A path from the root node to the 1-terminal represents a (possibly partial) variable assignment for which the represented Boolean function is true. As the path descends to a low (or high) child from a node, then that node's variable is assigned to 0 (resp. 1). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Binary decision diagram」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.